package basic.study.wantOffer.chapter5;

/**
 * @ClassName Problem53
 * @Description 数字在排序数组中出现的次数
 * @Company inspur
 * @Author Kevin
 * @Date 2020/6/6 17:41
 * @Version 1.0
 */
public class Problem53 {
    /**
     * 这个问题可以分解成找到数字的第一个位置和最后一个位置
     */
    public int findOccurTimes(int[] arr, int num) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int startIndex = findFirstPos(arr, 0, arr.length-1, num);
        int endIndex = findLastPos(arr, 0, arr.length-1, num);
        return endIndex - startIndex + 1;
    }

    public int findFirstPos(int[] arr, int start, int end,int num) {
        if (start > end) return -1;
        int mid = start + (end - start)>>1;
        if (arr[mid] < num) {
            start = mid + 1;
        } else if (arr[mid] > num) {
            end = mid -1;
        } else {//num == arr[mid]
            if (mid == 0 || arr[mid -1] != num) return mid;
            else end = mid + 1;
        }
        return findFirstPos(arr, start, end, num);
    }

    public int findLastPos(int[] arr, int start, int end,int num) {
        if (start > end) return -1;
        int mid = start + (end - start)>>1;
        if (arr[mid] < num) {
            start = mid + 1;
        } else if (arr[mid] > num) {
            end = mid -1;
        } else {//num == arr[mid]
            if (mid == arr.length-1 || arr[mid + 1] != num) return mid;
            else start = mid + 1;
        }
        return findLastPos(arr, start, end, num);
    }


    /**
     * 解法二：寻找k+0.5和k-0.5的方法：
     */
    public int GetNumberOfK(int [] arr , int k) {
        if(arr==null || arr.length<=0)
            return 0;
        int first = getLoc(arr, k , k-0.5);
        int last = getLoc(arr,k,k+0.5);
        return last-first;
    }

    private int getLoc(int[]arr, int k, double m){ //同样是二分查找
        int start=0,end=arr.length-1;
        while(start<=end){
            int mid=(start+end)>>1;
            if(arr[mid]>m){
                end=mid-1;
            }else{
                start=mid+1;
            }
        }
        return start;
    }

    /**
     * 0~n-1中缺失的数字
     */
    class Problem53_1 {
        int getMissingNumber(int[] arr) {
            int len = arr.length;
            return findMiss(arr, 0, arr.length-1);
        }

        int findMiss(int[]arr, int start, int end) {
            int mid = start + (end - start) >> 1;
            while (start <= end) {
                if (arr[mid] == mid) {
                    start = mid + 1;
                } else if (arr[mid] < mid) {
                    if (mid == 0 || arr[mid-1] == mid -1) return mid;
                    else end = mid -1;
                }
            }
            if (start == arr.length-1) return arr.length-1;

            return -1;
        }
    }

    /**
     * 数组中数值和下标相等的元素
     */
    class Problem50_2 {
        int getNumberSameAsIndex(int[] arr) {
            if (arr == null || arr.length == 0) return -1;

            int end = arr.length -1;
            int start = 0;
            while (start <= end) {
                int mid = start + (end - start) >> 1;
                if (arr[mid] == mid) {
                    return mid;
                } else if (arr[mid] > mid) {
                    end = mid -1;
                } else {
                    start = mid + 1;
                }
            }

            return -1;
        }
    }
}
